package main

import "fmt"

// https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150
// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
func main() {
	var nums []int
	nums = []int{2, 3, 0, 1, 4}
	nums = []int{2, 3, 1, 1, 4}
	val := jump2(nums)
	fmt.Println(val)
}

func jump45(nums []int) int {
	end := len(nums) - 1
	// 从头往后找到第一个能跳到 pos 的
	pos := end
	step := 0
	for pos > 0 {
		for i := 0; i < pos; i++ {
			if i+nums[i] >= pos {
				pos = i
				step++
				break
			}
		}
	}
	return step
}

// 思路： 从头开始找第一个能跳到末尾的下标 x，然后再从头找第一个能跳到x的，以此类推
func jump2(nums []int) int {
	pos := len(nums) - 1
	ans := 0
	for pos > 0 {
		for i := 0; i < pos; i++ {
			if i+nums[i] >= pos {
				pos = i
				ans++
				break //找到了
			}
		}
	}
	return ans
}
